public class Percolation {
    public int numberOfOpenSites=0;
    public boolean openState[];          //记录每个位的开放情况 0表示关闭 1表示打开
    public union_find site;          //用以判断连通
    public int number;               //一行有多少个数
    // creates n-by-n grid, with all sites initially blocked
    public Percolation(int n)
    {
       number=n;
       openState=new boolean[n*n+1];        //额外给一个位置浪费掉，让其和逻辑位置对应
       for(int i=0;i<=n*n;i++)
       {
        openState[i]=false;          //初始化成关闭        
       }
       site=new union_find(n*n+2);        //两个额外的虚构位，一个放0位置和所有第一行相连，一个放末尾和最后一行相连
       for(int i=1;i<=n;i++)
       {
         site.union(i, 0);
         site.union(n*(n-1)+i, n*n+1);
       }  
    }


    // opens the site (row, col) if it is not open already
    public void open(int row, int col)
    {
       openState[number*(row-1)+col]=true;
       int around_row,around_col;
       for(int i=-1;i<=1;i++)
       {
        for(int j=-1;j<=1;j++)
        {
           if(i==0&&j==0)
           {
            continue;
           }
           if((i==-1||i==1)&&(j==-1||j==1))
           {
            continue;
           }
           around_row=row+i;
           around_col=col+j;
           if(around_row>=1&&around_row<=number&&around_col>=1&&around_col<=number)    //经过i和j之后的坐标既不能小于1也不能大于number
           {
             if(openState[number*(around_row-1)+around_col])  //如果这个周围的点也是开放的，那么连接
             {
                site.union(number*(around_row-1)+around_col,number*(row-1)+col);
             }
           }
        }
       }
    }

    // is the site (row, col) open?
    public boolean isOpen(int row, int col)
    {
        return openState[number*(row-1)+col];
    }

    // is the site (row, col) full?
    public boolean isFull(int row, int col)
    {
        return site.connected(number*(row-1)+col, 0);         
    }

    // returns the number of open sites
    public int numberOfOpenSites()
    {
        return numberOfOpenSites;
    }

    // does the system percolate?
    public boolean percolates()
    {
        return site.connected(0, number*number+1);
    }
}
